#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
char* removeDuplicates(char* s) {
    int k = strlen(s);
    char* x = malloc(k * sizeof(char));
    int top = 0;
    for (int i = 0; i < k; i++) {
        if (top > 0 && x[top - 1] == s[i]) {
            top--;
        }
        else {
            x[top++] = s[i];
        }
    }
    x[top] = '\0';
    return x;
}
char* makeGood(char* s) {
    int k = strlen(s);
    char* x = malloc((k + 1) * sizeof(char));
    int top = 0;
    for (int i = 0; i < k; i++) {
        if (top > 0 && (s[i] == x[top - 1] - 32 || s[i] == x[top - 1] + 32)) {
            top--;
        }
        else {
            x[top++] = s[i];
        }
    }
    x[top] = '\0';
    return x;
}
void preorder(struct TreeNode* root, int* returnSize, int* b, int** a) {
    if (root == NULL)
        return;
    if ((*returnSize) >= (*b)) {
        int* c = realloc(*a, (*b) * 2 * (sizeof(int)));
        if (c == NULL)
        {
            printf("realloc failure\n");
            exit(-1);
        }
        *a = c;
        (*b) *= 2;
    }
    (*a)[(*returnSize)++] = root->val;
    preorder(root->left, returnSize, b, a);
    preorder(root->right, returnSize, b, a);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* a = malloc(4 * sizeof(int));
    int* b = malloc(sizeof(int));
    *b = 4;
    preorder(root, returnSize, b, &a);
    return a;
}
void p1() {
    char a[] = { 'a','b','b','a','c','a' ,'\0'};
    char* b = malloc(sizeof(char));
    b = removeDuplicates(a);
    for (int i = 0; b[i] != '\0'; i++) {
        printf("%c ", b[i]);
    }
    printf("\n");
}
void p2() {
    char a[] = { 'l','e','E','e','e','t','c','o','d','e' ,'\0'};
    char* b = malloc(sizeof(char));
    b = makeGood(a);
    for (int i = 0; b[i] != '\0'; i++) {
        printf("%c ", b[i]);
    }
    printf("\n");
}
void p3() {
    struct TreeNode* q1 = malloc(sizeof(struct TreeNode));
    q1->val = 1;

    struct TreeNode* q2 = malloc(sizeof(struct TreeNode));
    q2->val = 2;

    struct TreeNode* q3 = malloc(sizeof(struct TreeNode));
    q3->val = 3;
    q3->left = NULL;

    q1->left = q2;
    q1->right = q3;

    struct TreeNode* q4 = malloc(sizeof(struct TreeNode));
    q4->val = 4;
    q4->left = NULL;
    q4->right = NULL;

    struct TreeNode* q5 = malloc(sizeof(struct TreeNode));
    q5->val = 5;

    q2->left = q4;
    q2->right = q5;

    struct TreeNode* q6 = malloc(sizeof(struct TreeNode));
    q6->val = 6;
    q6->left = NULL;
    q6->right = NULL;

    struct TreeNode* q7 = malloc(sizeof(struct TreeNode));
    q7->val = 7;
    q7->left = NULL;
    q7->right = NULL;

    q5->left = q6;
    q5->right = q7;

    struct TreeNode* q8 = malloc(sizeof(struct TreeNode));
    q8->val = 8;
    q8->right = NULL;

    q3->right = q8;
    
    struct TreeNode* q9 = malloc(sizeof(struct TreeNode));
    q9->val = 9;
    q9->left = NULL;
    q9->right = NULL;
    q8->left = q9;
    int* x = malloc(sizeof(int));
    int* a = preorderTraversal(q1, x);
    for (int i = 0; i < *x; i++) {
        printf("%d ", a[i]);
    }
}
int main() {
    p1();
    p2();
    p3();
}